/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-04-18
 * Time:22:46
 */

/**
 * Jz8二叉树的下一个结点
 */

class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}

public class GetNext {
    /**
     * 这个思路时间复杂度是O(n)，空间复杂度是O(n)，不符合要求
     */
//    static int[] num = new int[50];
//    static int index = 0;
//    public static TreeLinkNode GetNext(TreeLinkNode pNode) {
//        if (pNode.next == null){
//            return null;
//        }
//        gainTheTreeNum(pNode);
//        int val = 0;
//        for (int i = 1; i < num.length; i++) {
//            if (pNode.val == num[i]){
//                val = num[i + 1];
//                break;
//            }
//        }
//        return new TreeLinkNode(val);
//    }
//
//    private static void gainTheTreeNum(TreeLinkNode pNode) {
//        if (pNode == null){
//            return;
//        }
//        GetNext(pNode.left);
//        num[index++] = pNode.val;
//        GetNext(pNode.right);
//    }

    /**
     * 针对中序遍历的性质，如果一个节点有右子树，
     * 那么它的下一个节点就是它右子树中最左边的节点；
     * 否则，如果它是它父节点的左子节点，那么它的下一个节点就是它的父节点；
     * 如果它是它父节点的右子节点，那么就一直往上找它的祖先节点，直到找到一个节点是它父节点的左子节点，那么这个节点的父节点就是它的下一个节点。
     * 具体实现可以分为以下几步：
     * 判断当前节点是否有右子树，如果有，就找到右子树中最左边的节点；
     * 如果当前节点没有右子树，就一直往上找它的祖先节点，直到找到一个节点是它父节点的左子节点，那么这个节点的父节点就是它的下一个节点；
     * 如果一直找到根节点都没有找到，那么当前节点就是中序遍历的最后一个节点，它的下一个节点就是null。
     * @param pNode
     * @return
     */
    public static TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        }
        // 如果有右子树，找到右子树中最左边的节点
        if (pNode.right != null) {
            TreeLinkNode node = pNode.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
        // 如果没有右子树，向上找父节点，直到找到一个节点是它父节点的左子节点
        while (pNode.next != null) {
            TreeLinkNode parent = pNode.next;
            if (parent.left == pNode) {
                return parent;
            }
            pNode = parent;
        }
        // 如果一直找到根节点都没有找到，说明当前节点是中序遍历的最后一个节点
        return null;
    }
}
